package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 89. 格雷编码
 * @date 2025/3/14 13:01
 */
public class E89 {

    /**
     * <h3>方法一：镜像反射法</h3>
     * @param n 待处理的数字
     * @return 格雷编码
     */
    public List<Integer> grayCode1(int n) {
        List<Integer> result = new ArrayList<>();
        result.add(0); // 初始序列
        for (int i = 1; i <= n; i++) {
            int size = result.size();
            int mask = 1 << (i - 1); // 在最高位加 1
            for (int j = size - 1; j >= 0; j--) {
                result.add(result.get(j) | mask); // 镜像反射并加 1
            }
        }
        return result;
    }

    // n = 3 时，序列为 [0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100]
    // 对应的index为：  [0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111]

    /**
     * <h3>方法二：公式法</h3>
     *
     * @param n 待处理的数字
     * @return 格雷编码
     */
    public List<Integer> grayCode2(int n) {
        int length = 1 << n;
        List<Integer> result = new ArrayList<>(length);
        for (int i = 0; i < length; i++)
            result.add(i ^ (i >> 1));
        return result;
    }
}
